package bit_pratice.day7;

/**
 * @author 美女
 * @date 2022/05/06 14:24
 **/
import java.util.*;
//括号匹配
public class Num2括号匹配 {
    public boolean chkParenthesis(String A, int n) {
        // write code here
        //字符串和长度n已知
        //长度为奇数时一定不是合法的
        if(n%2!=0){
            return false;
        }

        //长度为偶数时，用栈存放左括号，遍历到右括号时进行匹配，匹配成功括号出栈继续判断
        //遍历字符串途中有字母时一定false
        //最后遍历完毕，若栈为空则全部匹配完成，不为空匹配失败
        //注意遍历途中栈为空的情况，此时栈中无左括号但是字符串还未遍历完毕，明显左右括号匹配出错，false
        Stack<Character> stack=new Stack();
        //遍历字符串：因为不需要对字符串有任何修改，直接for-each循环遍历即可
        for(char ch:A.toCharArray()){
            if(ch=='('){
                stack.push(ch);
            }else if(ch==')'){
                //判断右括号存在时栈是否为空
                if(stack.isEmpty()){
                    return false;
                }
                //此时栈不为空，开始匹配，判断是否栈顶是'('
                //其实不用if直接出栈也可以，因为此时栈内只可能放了'('
                if(stack.peek()=='('){
                    stack.pop();
                }
            }else{
                //其他字符出现，直接false
                return false;
            }
        }
        return stack.isEmpty();
    }
}